package sort;


import graph.Graph;
import graph.ListGraph;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-15 21:23
 **/
public class TopologicalSort {
    public static final Object[][] TOPO = {
            {0, 2},
            {1, 0},
            {2, 5}, {2, 6},
            {3, 1}, {3, 5}, {3, 7},
            {5, 7},
            {6, 4},
            {7, 6}
    };


    /**
     * 生成有向图
     */
    private static Graph<Object, Double> directedGraph(Object[][] data) {
        Graph<Object, Double> graph = new ListGraph<>();
        for (Object[] edge : data) {
            if (edge.length == 1) {
                graph.addVertex(edge[0]);
            } else if (edge.length == 2) {
                graph.addEdge(edge[0], edge[1]);
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        //构建有向图
        Graph<Object, Double> graph = directedGraph(TOPO);
        //对图进行拓扑排序
        List<Object> list = graph.topologicalSort();
        System.out.println(list);
    }

}
